import java.util.Iterator;

import BucketMapping.BucketMapping;

/**
 * @author dave
 *
 */
public class StringSkiplist {
	private Item head;
	private Item tail;
		
	public static final int INF = java.lang.Integer.MAX_VALUE;
	public static final int NEGINF = java.lang.Integer.MIN_VALUE;
	
	private BucketMapping words;
	
	public StringSkiplist(){
		head = new Item(NEGINF, null, 0);
		tail = new Item(INF, null, 0);
		head.setNext(0,tail);
		tail.setPrevious(0,head);
		words = new BucketMapping(4000);
	}
	
	public void put(int date, String description){
		Item insert = new Item(date, description);
		
		//Double ends until they are greater than inserted height
		while(insert.getHeight()>head.getHeight())
			doubleEnds();
		
		Item before = head;
		Item after = tail;
		
		//find the before and afters of the level above the inserted item height
		for(int i=head.getHeight(); i>insert.getHeight(); i--){
			after = findAfterItem(date, i, before, after);
			before = after.getPrevious(i);
		}
		
		//insert the item in between the items of various levels
		for(int i=insert.getHeight(); i>=0; i--){
			after = findAfterItem(date, i, before, after);
			before = after.getPrevious(i);
			insert.setNext(i, after);
			insert.setPrevious(i,before);
			after.setPrevious(i, insert);
			before.setNext(i, insert);
		}
		
		wordHashItem(insert);
		//System.out.println(this);
	}
	
	public boolean containsKey(int date){
		Item before = head;
		Item after = tail;
		for(int i = head.getHeight(); i>=0; i--){
			after = findAfterItem(date, i, before, after);
			before = after.getPrevious(i);
			//System.out.println("At level "+i+" compared "+date+" to: "+before.getKey()+" "+after.getKey());
			if(after.getKey()==date)
				return true;
		}
		
		return false;
	}
	
	public String wordSearch(String word){
		word = word.toLowerCase();
		StringSkiplist sortedList = new StringSkiplist();
		Iterator it = words.get(word);
		if(it!=null){
			while(it.hasNext()){
				Item current = (Item)it.next();
				sortedList.put(current.getKey(), current.getData());
			}
			Item current = sortedList.head.getNext(0);
			String result = "";
			while(current.getKey() != INF){
				result += "\n"+current;
				current = current.getNext(0);
			}
			return result;
		}
		else
			return "Word "+word+" not found";
		
	}
	
	public String rangeSearch(int startKey, int endKey){
		Item start = findFirstOfKey(startKey, head, tail);
		Item stop = findLastOfKey(endKey, head, tail);
		if(start.getKey()>stop.getKey())
			return "Empty range";
		String result = "";
		while(start != stop && start != null){
			result += start+"\n";
			start = start.getNext(0);
		}
		
			//for last level
		result += start+"\n";
		
		return result;
			
	}
	
	public String remove(int date){
		Item current = findFirstOfKey(date, head, tail);
		String result = "";
		while(current.getKey() == date){
			result += "\n"+current;
			removeWordHash(current);
			for(int i=0; i<=current.getHeight(); i++){
				current.getPrevious(i).setNext(i,current.getNext(i));
				current.getNext(i).setPrevious(i,current.getPrevious(i));
			}
			current = current.getNext(0);
		}
		return result;
	}
	
	private void wordHashItem(Item insert){
		String[] wordArray = insert.getData().toLowerCase().split(" ");
		for(int i=0; i<wordArray.length; i++)
			words.put(wordArray[i], insert);
	}
	
	private void removeWordHash(Item remove){
		String[] wordArray = remove.getData().toLowerCase().split(" ");
		for(int i=0; i<wordArray.length; i++){
			Iterator current = words.get(wordArray[i]);
			while(current.hasNext()){
				if(current.next().equals(remove))
					current.remove();
			}
		}
	}
	
	private static Item findLastOfKey(int key, Item start, Item stop){
		int i;
		if(start.getHeight()>stop.getHeight())
			i=stop.getHeight();
		else
			i=start.getHeight();
		for(;i>=0; i--){
			stop = findAfterItem(key, i, start, stop);
			start = stop.getPrevious(i);
			while(stop.getKey()==key){
				stop = stop.getNext(i);
				start = start.getNext(i);
			}
		}
		return start;
	}
	
	//finds the first occurance of the key in the lowest level
	private static Item findFirstOfKey(int key, Item start, Item stop){
		int i;
		if(start.getHeight()>stop.getHeight())
			i=stop.getHeight();
		else
			i=start.getHeight();
		for(;i>=0; i--){
			stop = findAfterItem(key, i, start, stop);
			start = stop.getPrevious(i);
			
			//traverse any identical keys at the current level
			while(start.getKey()==key){
				start = start.getPrevious(i);
				stop = stop.getPrevious(i);
			}
		}
		return stop;
		
	}
	
	public String toString(){
		String result = "";
		int i = head.getHeight();
		
		//pass levels where there is no data
		while(head.getNext(i)==tail)
			i--;
		
		Item current;
		
		for(;i>=0;i--){
			current = head;
			result += "\nLevel "+i+":";
			while(current.getNext(i)!=tail){
				current = current.getNext(i);
				result += " "+current.getKey();
			}
		}
		
		return result;
	}
	
	private static Item findAfterItem(int key, int level, Item start, Item stop){
		Item current = start;
		
		//advances to item where key is >= found item 
		while(current.getKey()<key)
			current = current.getNext(level);
		return current;
	}
	private static Item findBeforeItem(int key, int level, Item start, Item stop){
		return findAfterItem(key, level, start, stop).getPrevious(level);
	}
	
	
	private void doubleEnds(){
		int newHeight;
		if(head.getHeight()==0)
			newHeight = 1;
		else
			newHeight = head.getHeight()+2;
		head.setHeight(newHeight);
		tail.setHeight(newHeight);
		
		//connect head and tail when the set is empty
		int i = head.getHeight();
		while(head.getNext(i)==null){
			head.setNext(i,tail);
			tail.setPrevious(i,head);
			i--;
		}
	}
}
